#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

class Solution 
{
public:
    int subarraySum(vector<int>& nums, int k) 
	{
		unordered_map<int, int> hash;
		hash[0] = 1;

		int sum = 0, ret = 0;
		for (auto x : nums)
		{
			sum += x;
			if (hash.count(sum - k)) ret += hash[sum - k];
			hash[sum]++;
		}
		return ret;
    }
};

void Test01()
{
	vector<int> nums = { 1, 4, 7, 1, 1, 2, 5, 8, 1, 1, 1, 3, 6, 9 };
	Solution s;
	cout << s.subarraySum(nums, 5);
}

int main()
{
	Test01();
	return 0;
}